package book_mianshizhinan.test1_6;

import java.util.Stack;

public class HanoiProblem {

	Stack<Integer> stackleft;
	Stack<Integer> stackmid;
	Stack<Integer> stackright;

	int actionCode = 0;
	int count = 0;

	public static void main(String[] args) {
		HanoiProblem hanoiProblem = new HanoiProblem();
		hanoiProblem.hanoiProblem(4);
		System.out.println(hanoiProblem.count + "��");
	}

	public void hanoiProblem(int N) {

		stackleft = new Stack<Integer>();
		stackmid = new Stack<Integer>();
		stackright = new Stack<Integer>();

		int tmp = N;
		// ��ʼ��
		while (tmp > 0) {
			stackleft.push(tmp);
			tmp--;
		}

		// ����ת��Ϊ����ôͨ��midջ����leftջ�����Ƶ�rightջ�����������������С��׼��
		// �����ڲ�����ԭ��

		while (stackright.size() != N) {
			move();
		}

	}

	private void move() {

		if (actionl2m())
			count++;
		if (actionm2l())
			count++;
		if (actionm2r())
			count++;
		if (actionr2m())
			count++;

	}

	private boolean actionl2m() {
		if (!stackleft.empty()
				&& (stackmid.empty() || stackleft.peek() < stackmid.peek())
				&& actionCode != 4) {
			System.out.println("move" + stackmid.push(stackleft.pop())
					+ "from left to middle");
			actionCode = 1;
			return true;
		}
		return false;
	}

	private boolean actionm2r() {
		if (!stackmid.empty()
				&& (stackright.empty() || stackmid.peek() < stackright.peek())
				&& actionCode != 3) {
			System.out.println("move" + stackright.push(stackmid.pop())
					+ "from middle to right");
			actionCode = 2;
			return true;
		}
		return false;
	}

	private boolean actionr2m() {
		if (!stackright.empty()
				&& (stackmid.empty() || stackright.peek() < stackmid.peek())
				&& actionCode != 2) {
			System.out.println("move" + stackmid.push(stackright.pop())
					+ "from right to middle");
			actionCode = 3;
			return true;
		}
		return false;
	}

	private boolean actionm2l() {
		if (!stackmid.empty()
				&& (stackleft.empty() || stackmid.peek() < stackleft.peek())
				&& actionCode != 1) {
			System.out.println("move" + stackleft.push(stackmid.pop())
					+ "from middle to left");
			actionCode = 4;
			return true;
		}
		return false;
	}

}
